class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        def func(k, n, memo):
            if (k, n) in memo:
                return memo[(k, n)]
            if k == 1:
                return n
            if n == 1 or n == 0:
                return n
            below = 1
            top = n
            ans = 2**31 - 1
            while below <= top:
                mid = (top + below) // 2
                left = func(k - 1, mid - 1, memo) + 1
                right = func(k, n - mid, memo) + 1
                temp = max(left, right)
                if left < right:
                    below = mid + 1
                else:
                    top = mid - 1
                ans = min(ans, temp)
            memo[(k, n)] = ans
            return ans

        memo = {}
        res = func(k, n, memo)
        return res
